# 第 4 节 链表
# 链表类
class Node:
    def __init__(self, data):
        self.data = data
        self.node = None


if __name__ == '__main__':
    print('main')
    head = None
    # q = Node(0)
    # 构建链表
    while True:
        a = input("输入数字")
        if a == 'exit':
            break
        n = Node(a)
        if head is None:
            head = n
        else:
            q.node = n
        q = n
    # 链表中插入数字
    b = input("待插入数字")
    q = head  # 从链表头部开始遍历
    p = Node(b)
    while q is not None:
        # 插入头部
        if q.data > b:
            p.node = q
            head = p
            break  # 插入完毕退出循环
        # 插入中部
        if q.node is not None and q.node.data > b:
            p.node = q.node
            q.node = p
            break  # 插入完毕退出循环
        # 插入尾部
        if q.node is None:
            q.node = p
            break  # 插入完毕退出循环
        q = q.node

    # 打印链表
    q = head  # 从链表头部开始遍历
    while q is not None:
        print(q.data, end=' ')
        q = q.node
